Convex Optimization: Beyond Basic Convexity: Preservation through Pointwise Supremum

While basic convexity covers sums and scaling, the preservation of convexity through the pointwise supremum is a foundational operation for constructing non-trivial convex functions and establishing duality. It states that even if we have an uncountably infinite family of convex functions, their "upper envelope" remains convex. This bridge allows us to analyze complex convex shapes using simple linear components.

1. The Technical Definition

For a family of functions $\{f(\cdot, y) \mid y \in \mathcal{A}\}$, the pointwise supremum is defined as:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

The domain of this function is the set of points where all functions in the family are defined and the supremum is finite:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ for all } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

The Epigraph Perspective

Geometrically, the epigraph of the supremum function is the intersection of the individual epigraphs:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Since each individual epigraph is a convex set (due to the convexity of $f(x, y)$ in $x$), and the intersection of any number of convex sets is itself convex, the convexity of $g(x)$ is guaranteed.

2. Significant Examples

Support Function: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. This function is always convex, regardless of whether the set $C$ is convex or not, because it is the supremum of linear (affine) functions of $y$.
Distance to Farthest Point: $f(x) = \sup_{y \in C} \|x - y\|$. Even for an irregularly shaped set $C$, $f(x)$ is convex in $x$ because the norm is a convex function of $x$.
Maximum Eigenvalue: For a symmetric matrix $X$, $f(X) = \lambda_{\max}(X)$ is convex. This is derived from the Rayleigh quotient: $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. It is the supremum of linear functions of $X$.

Theorem: Representation by Affine Functions

Theorem

Almost every convex function can be expressed as the pointwise supremum of a family of affine functions (global underestimators).

Intuition

At every point $x_0$, a convex function $f$ has a supporting hyperplane (an affine function $h(x) = f(x_0) + g^T(x-x_0)$). By taking the supremum of all such supporting hyperplanes, we reconstruct the function $f$ exactly.

🎯 Core Principle

The pointwise supremum preserves convexity and the pointwise infimum preserves concavity. This is the secret behind the convexity of norms, spectral functions, and dual problems.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ is convex if } f(\cdot, y) \text{ is convex } \forall y$$

QUESTION 1

If $f_1(x), f_2(x), \dots, f_n(x)$ are convex functions, what can we say about $g(x) = \max\{f_1(x), \dots, f_n(x)\}$?

$g(x)$ is always convex.

$g(x)$ is convex only if all $f_i$ are linear.

$g(x)$ is concave.

$g(x)$ is only quasiconvex.

QUESTION 2

The support function $S_C(y) = \sup_{x \in C} y^T x$ is convex in $y$ even if $C$ is a non-convex set. Why?

Because $y^T x$ is linear (and thus convex) in $y$ for any fixed $x$.

Because the set $C$ is automatically treated as its convex hull.

Because the inner product is always a positive function.

Support functions are only convex if $C$ is bounded.

QUESTION 3

What is the relationship between the epigraph of $g(x) = \sup f_i(x)$ and the individual epigraphs $\text{epi } f_i$?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

There is no direct relationship.

QUESTION 4

The spectral norm of a matrix $\|X\|_2 = \sigma_{\max}(X)$ is convex because...

It is the supremum of the convex functions $\|Xv\|_2$ over unit vectors $v$.

The sum of singular values is always convex.

All norms are linear functions.

Matrix functions are always convex on the positive semidefinite cone.

QUESTION 5

If we take the pointwise infimum of a family of concave functions, what is the result?

A concave function.

A convex function.

A linear function.

It depends on the domain.

Challenge: Duality and Conjugate Functions

MATH008 Advanced Analysis

In convex analysis, the conjugate function $f^*$ is defined via the pointwise supremum of affine functions: $f^*(y) = \sup_x (y^T x - f(x))$. This transformation is vital for dual optimization problems.

[Short Answer] Second-order condition for convexity. Prove that a twice differentiable function $f$ is convex if and only if its domain is convex and $\nabla^2 f(x) \succeq 0$ for all $x \in \mathbf{dom} f.

Solution: By restricting $f$ to an arbitrary line $g(t) = f(x + tv)$, convexity of $f$ is equivalent to $g''(t) \geq 0$ for all $v$ and all $t$ such that $x+tv \in \text{dom } f$. Since $g'(t) = \nabla f(x + tv)^T v$ and $g''(t) = v^T \nabla^2 f(x + tv) v$, the condition $g''(t) \geq 0$ for all $v$ is equivalent to the Hessian matrix being positive semidefinite: $\nabla^2 f(x) \succeq 0$.

[Short Answer] Gradient and Hessian of conjugate function. Suppose $\bar{y}$ and $\bar{x}$ are related by $\bar{y} = \nabla f(\bar{x})$, and that $\nabla^2 f(\bar{x}) \succ 0$. (a) Show that $\nabla f^*(\bar{y}) = \bar{x}$. (b) Show that $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}$. (Required Output: 250 words)

Instructor Reference Answer: To address part (a), we recall the definition of the conjugate function $f^*(y) = \sup_x (y^T x - f(x))$. For a fixed $y = \bar{y}$, if $f$ is differentiable and convex, the supremum is attained at the point where the gradient of the objective $h(x) = \bar{y}^T x - f(x)$ vanishes. Setting $\nabla_x (\bar{y}^T x - f(x)) = 0$ yields $\bar{y} = \nabla f(x)$. Given the problem states $\bar{y} = \nabla f(\bar{x})$, it follows that $\bar{x}$ is the maximizer. By the property of the conjugate at the point of optimality, we have $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. Differentiating both sides with respect to $\bar{y}$ and applying the envelope theorem (or the fact that $\bar{x}$ is the optimizer), we obtain $\nabla f^*(\bar{y}) = \bar{x}$. This confirms that the gradient of the conjugate function acts as the inverse mapping of the gradient of the original function.

For part (b), we differentiate the relationship $\nabla f^*(\nabla f(x)) = x$ with respect to $x$ using the chain rule. This gives $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, where $I$ is the identity matrix. Substituting $\bar{y} = \nabla f(\bar{x})$, we get $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Since we are given $\nabla^2 f(\bar{x}) \succ 0$, the Hessian is invertible. Thus, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}$. This elegant result shows that the local curvature of the conjugate function is the reciprocal (or inverse matrix) of the curvature of the original function at corresponding points. This relationship is central to the analysis of Newton-type methods in dual space and the understanding of Legendre transforms in physics and optimization.